package com.zp.self.module.level_4_算法练习.数据结构.链表;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * @author By ZengPeng
 */
public class 力扣_147_对链表进行插入排序 {
    @Test
    public void main() {

        ListNode listNode = insertionSortList(ListNode.getNode());
        System.out.println(listNode);
    }

    /**
    题目：给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
     插入排序 算法的步骤:
     插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
     每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
     重复直到所有输入数据插入完为止。
     下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。
     每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。
     对链表进行插入排序。

     示例 1：
     输入: head = [4,2,1,3]
     输出: [1,2,3,4]

     示例 2：
     输入: head = [-1,5,3,4,0]
     输出: [-1,0,3,4,5]


    分析：【P 💔💔】
       1.遍历：记录虚拟链表头virtual，上一个节点pro，对比节点compare,不断与当前节点current作比较，
                当找到大于自己的节点时: pro.next = current ,current.next=compare  --时间、空间复杂度O(n*n)、O(1)
                --执行用时：2 ms, 在所有 Java 提交中击败了99.32%的用户
       2.快排：获取所有节点到list,对值进行sort排序，然后在组装成链表  --时间、空间复杂度O(n*logn)、O(n)
                --执行用时：5 ms, 在所有 Java 提交中击败了32.69%的用户
                --时长：4分钟

    边界值 & 注意点：
       1.
     **/
    public ListNode insertionSortList(ListNode head) {
        //1.遍历：记录虚拟链表头virtual，上一个节点pro，对比节点compare,不断与当前节点current作比较，
        ListNode virtual = new ListNode();
        virtual.next=head;
        ListNode pro,temp,lastNode=head;
        head=head.next;
        while (head!=null){
            if(head.val>lastNode.val){
                lastNode.next=head;
                lastNode=head;
                head=head.next;
            }else {
                pro = virtual;
                while (head.val>pro.next.val) {
                    pro=pro.next;
                }
                temp = head.next;
                head.next=pro.next;
                pro.next = head ;
                head=temp;
            }
        }
        lastNode.next=null;
        return virtual.next;

        // 2.快排：获取所有节点到list,对值进行sort排序，然后在组装成链表  --时间、空间复杂度O(n*logn)、O(n)
        /*List<ListNode> list= new ArrayList<>();
        while (head!=null){
            list.add(head);
            head=head.next;
        }
        list.sort(Comparator.comparingInt(o -> o.val));
        ListNode virtual = new ListNode(),pro=virtual;
        for (ListNode listNode : list) {
            pro.next=listNode;
            pro=listNode;
        }
        pro.next=null;
        return virtual.next;*/
    }
}
